package zw_1_100.zw_5_最长回文子串;


class Solution {

    public static void main(String[] args) {
        String s = "adcdgb";
        String s1 = longestPalindrome(s);
        System.out.println(s1);
    }


//    public String longestPalindrome(String s) {
//        if (s == null || s.length() == 0) {
//            return "";
//        }
////         保存起始位置，测试了用数组似乎能比全局变量稍快一点
//        int[] range = new int[2];
//        char[] str = s.toCharArray();
//        for (int i = 0; i < s.length(); i++) {
////             把回文看成中间的部分全是同一字符，左右部分相对称
////             找到下一个与当前字符不同的字符
//            i = findLongest(str, i, range);
//        }
//        return s.substring(range[0], range[1] + 1);
//    }
//
//    public static int findLongest(char[] str, int low, int[] range) {
////         查找中间部分
//        int high = low;
//        while (high < str.length - 1 && str[high + 1] == str[low]) {
//            high++;
//        }
////         定位中间部分的最后一个字符
//        int ans = high;
////         从中间向左右扩散
//        while (low > 0 && high < str.length - 1 && str[low - 1] == str[high + 1]) {
//            low--;
//            high++;
//        }
////         记录最大长度
//        if (high - low > range[1] - range[0]) {
//            range[0] = low;
//            range[1] = high;
//        }
//        return ans;
//    }


    /**
     * 解法 3: 暴力破解优化
     * 时间复杂度：两层循环 O(n²)。
     * 空间复杂度：用二维数组 P 保存每个子串的情况 O(n²)。
     *
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        int n = s.length();
        String res = "";
        boolean[] P = new boolean[n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= i; j--) {
                P[j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || P[j - 1]);
                if (P[j] && j - i + 1 > res.length()) {
                    res = s.substring(i, j + 1);
                }
            }
        }
        return res;
    }



    /**
     * 解法 2: 最长公共子串
     * 根据回文串的定义，正着和反着读一样，那我们是不是把原来的字符串倒置了，然后找最长的公共子串就可以了。
     * 例如 S = "caba" ，S = "abac"，最长公共子串是 "aba"，所以原字符串的最长回文串就是 "aba"。
     * 关于求最长公共子串（不是公共子序列），有很多方法，这里用动态规划的方法，
     * 整体思想就是，申请一个二维的数组初始化为 0，然后判断对应的字符是否相等，相等的话
     * arr[i][j]=arr[i-1][j-1]+1。
     * 当 i = 0 或者 j = 0 的时候单独分析，字符相等的话arr[i][j]就赋为 1 。
     * arr[i][j] 保存的就是公共子串的长度。
     *      S="abc435cba"，S="abc534cba"，最长公共子串是 "abc" 和 "cba"，但很明显这两个字符串都不是回文串。
     *      所以我们求出最长公共子串后，并不一定是回文串，我们还需要判断该字符串倒置前的下标和当前的字符串下标是不是匹配。
     *
     * @param s
     * @return
     */
//    public static String longestPalindrome(String s) {
//        if (s.equals(""))
//            return "";
//        String origin = s;
//        String reverse = new StringBuffer(s).reverse().toString();
//        int length = s.length();
//        int[] arr = new int[length];
//        int maxLen = 0;
//        int maxEnd = 0;
//        for (int i = 0; i < length; i++)
//        /**************修改的地方***************************/
//            for (int j = length - 1; j >= 0; j--) {
//                /**************************************************/
//                if (origin.charAt(i) == reverse.charAt(j)) {
//                    if (i == 0 || j == 0) {
//                        arr[j] = 1;
//                    } else {
//                        arr[j] = arr[j - 1] + 1;
//                    }
//                    /**************修改的地方***************************/
//                    //之前二维数组，每次用的是不同的列，所以不用置 0 。
//                } else {
//                    arr[j] = 0;
//                }
//                /**************************************************/
//                if (arr[j] > maxLen) {
//                    int beforeRev = length - 1 - j;
//                    if (beforeRev + arr[j] - 1 == i) {
//                        maxLen = arr[j];
//                        maxEnd = i;
//                    }
//
//                }
//            }
//        return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
//    }


    /**
     * 暴力解法
     * 时间复杂度：两层 for 循环 O(n²），for 循环里边判断是否为回文 O(n），所以时间复杂度为 O(n³)。
     * 空间复杂度：O(1），常数个变量。
     *
     * @param s
     * @return
     */
//    public static String longestPalindrome(String s) {
//        String ans = "";
//        int max = 0;
//        for (int i = 0; i < s.length(); i++) {
//            for (int j = i + 1; j <= s.length(); j++) {
//                String str = s.substring(i, j);
//                if (isPalindromic(str) && str.length() > max) {
//                    ans = str;
//                    max = str.length();
//                }
//            }
//        }
//        return ans;
//    }
//
//    public static boolean isPalindromic(String s) {
//        int len = s.length();
//        for (int i = 0; i < len / 2; i++) {
//            if (s.charAt(i) != s.charAt(len - i - 1)) {
//                return false;
//            }
//        }
//        return true;
//    }

}
